/// https://leetcode-cn.com/problems/4sum/
pub struct Solution;

impl Solution {
    pub fn four_sum(mut nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let n = nums.len();
        let mut v: Vec<Vec<i32>> = Vec::new();

        if n < 4 {
            return v;
        }
        nums.sort();

        if nums.iter().take(4).sum::<i32>() > target
           || nums.iter().rev().take(4).sum::<i32>() < target
        {
            return v;
        }

        let mut left: usize;
        let mut right: usize;
        let mut sum: i32;

        for i in 0..n - 3 {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }
            if nums[i..i + 4].iter().sum::<i32>() > target {
                break;
            }
            if nums[i] + nums[n - 3..].iter().sum::<i32>() < target {
                continue;
            }

            for j in i + 1..n - 2 {
                if j > i + 1 && nums[j] == nums[j - 1] {
                    continue;
                }
                left = j + 1;
                right = n - 1;

                while left < right {
                    sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if sum == target {
                        v.push(vec![nums[i], nums[j], nums[left], nums[right]]);

                        while left < right && nums[right] == nums[right - 1] {
                            right -= 1;
                        }
                        while left < right && nums[left] == nums[left + 1] {
                            left += 1;
                        }

                        right -= 1;
                        left += 1;
                    } else if sum > target {
                        right -= 1;
                    } else {
                        left += 1;
                    }
                }
            }
        }
        v
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>, i32) -> Vec<Vec<i32>> {
        let v = vec![1, 0, -1, 0, -2, 2];
        assert_eq!(f(v, 0), vec![vec![-2, -1, 1, 2], vec![-2, 0, 0, 2], vec![-1, 0, 0, 1]]);

        let v = vec![-2, -1, -1, 1, 1, 2, 2];
        assert_eq!(f(v, 0), vec![vec![-2, -1, 1, 2], vec![-1, -1, 1, 1]]);

        let v = vec![2, 2, 2, 2];
        assert_eq!(f(v, 8), vec![vec![2, 2, 2, 2]]);
    }

    bench!(assert Solution::four_sum);
}
